﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SAI
{
    class ID
    {
        public static Metrics metrics = new Metrics();
        public static Node IDDFS(Node start, Node goal)
        {
            metrics.clearMetrics();
            DateTime dtStart = DateTime.Now;
            int depth = 0;
            start.visited();
            start.Level = 0;
            while (true)
            {
                metrics.Size = depth;
                Node result = DLS(start, goal, depth);
                if (result == goal)
                {
                    metrics.Time = (DateTime.Now - dtStart).TotalSeconds;
                    return result;
                }
                if (depth % 5 == 0)
                    Console.Write(depth + ", ");
                depth++;
            }
        }

        private static Node DLS(Node node, Node goal, int depth)
        {
            metrics.NodesGenerated++;
            if (depth == 0 && node == goal)
                return node;
            else if (depth > 0)
            {
                foreach (Node n in node.getOutNeighbors())
                {
                    Node result = null;
                    if (n.Level > node.Level)
                    {
                        if (!metrics.DupNodes.ContainsKey(node.ID))
                            metrics.DupNodes.Add(node.ID, 1);
                        else
                            metrics.DupNodes[node.ID]++;
                        
                        n.Level = node.Level + 1;
                        n.Parent = node;
                        result = DLS(n, goal, depth - 1);
                    }
                    if (result != null)
                        return result;
                }
                metrics.NodesExpanded++;
            }
            return null;
        }

        public static Node IDA(Node start, Node goal, int depth)
        {
            Stack<Node> s = new Stack<Node>();
            start.Level = 0;
            s.Push(start);
            start.visited();
            while (s.Count > 0)
            {
                Node node = s.Pop();
                if (node == goal)
                    return node;
                if (node.Level > depth)
                    continue;

                foreach (Node n in node.getOutNeighbors())
                {
                    if (!n.Visited)
                    {
                        n.visited();
                        n.Parent = node;
                        n.Level = node.Level + 1;
                        s.Push(n);
                    }
                }
            }
            return null;
        }

    }
}
